/*******************************/
/**** Author : Vo Quang Hoa ****/
/****     (c) 2010          ****/
/*******************************/
#include<stdio.h>
#include<conio.h>
#define max 10000
int queue[2*max+10],last=0,first=0;
int change[max+1][max+1],action[max*max],total=0;
int resultx=0,resulty=0,finishSuccess=0;
int tracex[max+1][max+1],tracey[max+1][max+1];
int X,Y,Z;
char *str[]={"","Do tu X --> Y : ","Do tu Y --> X : ","Do X ra ngoai : ","Do Y ra ngoai : ","Do day binh X : ","Do day binh Y : "};
int changex(int x,int y,int type){
    switch(type){
        // x-->y
        case 1:return x+y<=Y?0:x+y-Y;
        // y-->x
        case 2:return x+y>X?X:x+y;
        // x-->0
        case 3:return 0;
        // y-->0
        case 4:return x;
        // x-->X
        case 5:return X;
        // y-->Y
        case 6:return x;
    }
}   
int changey(int x,int y,int type){
    switch(type){
        // x-->y
        case 1:return x+y<=Y?x+y:Y;
        // y-->x
        case 2:return x+y>X?x+y-X:0;
        // x-->0
        case 3:return y;
        // y-->0
        case 4:return 0;
        // x-->X
        case 5:return y;
        // y-->Y
        case 6:return Y;
    }
}  
void bfs(){
    int ux,uy,vx,vy,i;
    queue[++last]=0;
    queue[++last]=0;
    do{
        ux=queue[++first];
        uy=queue[++first];
        for(i=1;i<=6;i++){
            
            vx=changex(ux,uy,i);
            vy=changey(ux,uy,i);
            if(change[vx][vy]==0){
                tracex[vx][vy]=ux;
                tracey[vx][vy]=uy;
                
                queue[++last]=vx;
                queue[++last]=vy;
                
                change[vx][vy]=i;
                if(vx==Z || vy ==Z){
                    resultx=vx;
                    resulty=vy;
                    finishSuccess=1;
                    return;
                }
            }
        }
    }while(first<last);
}
void output(){
    int x=resultx,y=resulty,x0,y0,type,i;
    if(!finishSuccess){
        printf("No way ! :(");
        return;
    }
    do{
        action[++total]=change[x][y];
        x0=tracex[x][y];
        y0=tracey[x][y];
        
        x=x0;y=y0;
    }while(x!=0 || y!=0);
    i=1;
    printf("Bat dau 2 binh rong\n");
    while(total>0){
        type=action[total];
        x0=changex(x,y,type);
        y0=changey(x,y,type);
        x=x0;y=y0;
        printf("\nBuoc %2d : %s %3d %3d",i++,str[type],x,y);
        total--;
    }   
    printf("\n\nSau %d buoc, ta lay duoc %d lit :D",i-1,Z);
}
int main(){
    //X=10;Y=3;Z=5;
    printf("Nhap dung tich binh thu nhat (<=100) : ");scanf("%d",&X);
    printf("Nhap dung tich binh thu hai  (<=100) : ");scanf("%d",&Y);
    printf("Nhap dung tich can dong      (<=100) : ");scanf("%d",&Z);
    printf("\n\n");
    printf("De bai : Co 2 binh co dung tich %d va %d lit.\n",X,Y);
    printf("Tim cach do de lay duoc %d lit\n=============================\n",Z);
    bfs();
    output();
    getch();
    return 0;
}  
        
